//========================================//
// Estructura de Datos y Algoritmos 2010
//========================================//
#ifndef __STDLIB_H
	#include<STDLIB.H>
#endif

#define EXIT_ERROR 255
const int ARBOLNULO = NULL;
//========================================//

template<class T>
class Nodo {
	public:
		T elemento;
		Nodo<T> *HIzq;
		Nodo<T> *HDer;
};

//========================================//

template<class T>
class ArbolBin{
		Nodo<T> *raiz;
		void talarR(Nodo<T> *pos);
	public:
		ArbolBin();
		Nodo<T>* padre(Nodo<T>*,Nodo<T>*);
		Nodo<T>* *hijoIzq(Nodo<T>*);
		Nodo<T>* *hijoDer(Nodo<T>*);
		T recuperar(Nodo<T>*);
		Nodo<T>* *raizArbol();
		void asignarNodo(T,Nodo<T>* &);
		void modificarDato(Nodo<T>*,T);
		void talar();
};

//========================================//

template<class T>
ArbolBin<T>::ArbolBin() {
	raiz = ARBOLNULO;
};

//========================================//

template<class T>
Nodo<T>* *ArbolBin<T>::raizArbol() {
	return(&raiz);
};

//========================================//

template<class T>
void ArbolBin<T>::asignarNodo(T x, Nodo<T>* &p) {
	if(p == ARBOLNULO) {
		p = new Nodo<T>;
		p->HIzq = ARBOLNULO;
		p->HDer = ARBOLNULO;
	}
	p->elemento = x;
};
//========================================//

template<class T>
Nodo<T>* ArbolBin<T>::padre(Nodo<T> *p,Nodo<T> *A) {
	Nodo<T> *R;
	if((A == ARBOLNULO) || (p == ARBOLNULO)) R = ARBOLNULO;
	else if(A->HIzq == p || A->HDer == p) R = A;
	else {
		R = padre(p,A->HIzq);
		if(R == ARBOLNULO) R = padre(p,A->HDer);
	}
	return R;
};

//========================================//

template<class T>
Nodo<T>* *ArbolBin<T>::hijoIzq(Nodo<T> *p) {
	if(p == ARBOLNULO) {
		fprintf(stderr,"HA INTENTADO OBTENER EL HIJO IZQ. DE UN NODO INEXISTENTE");
		exit(EXIT_ERROR);
	}
	return(&(p->HIzq));
};

//========================================//

template<class T>
Nodo<T>* *ArbolBin<T>::hijoDer(Nodo<T> *p) {
	if(p == ARBOLNULO) {
		fprintf(stderr,"HA INTENTADO OBTENER EL HIJO DER. DE UN NODO INEXISTENTE");
		exit(EXIT_ERROR);
	}
	return(&(p->HDer));
};

//========================================//

template<class T>
T ArbolBin<T>::recuperar(Nodo<T> *p) {
	T r;
	if(p != ARBOLNULO) r = p->elemento;
	else {
		fprintf(stderr,"HA INTENTADO RECUPERAR EN UNA POSICION INEXISTENTE");
		exit(EXIT_ERROR);
	}
	return(r);
};

//========================================//

template<class T>
void ArbolBin<T>::modificarDato(Nodo<T> *p,T x) {
	if(p != ARBOLNULO) p->elemento = x;
	else {
		fprintf(stderr,"HA INTENTADO MODIFICAR EN UNA POSICION INEXISTENTE");
		exit(EXIT_ERROR);
	}
};

//========================================//

template<class T>
void ArbolBin<T>::talar() {
	if(raiz != ARBOLNULO) {
		talarR(raiz);
		delete raiz;
		raiz = ARBOLNULO;
	}
};

//========================================//

template<class T>
void ArbolBin<T>::talarR(Nodo<T> *p) {
	if(p != ARBOLNULO){
		if(p->HIzq != ARBOLNULO) {
			talarR(p->HIzq);
			delete p->HIzq;
			p->HIzq = ARBOLNULO;
		}
		if(p->HDer != ARBOLNULO) {
			talarR(p->HDer);
			delete p->HDer;
			p->HDer = ARBOLNULO;
		}
	}
};
